package com.myc.subjects.binarytreeandrecurtion;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

/**
 * 二叉树遍历
 *
 * 1.深度优先遍历（DFS）
 * 中序遍历：即左-根-右遍历，对于给定的二叉树根，寻找其左子树；对于其左子树的根，再去寻找其左子树；递归遍历，直到寻找最左边的节点i，其必然为叶子，然后遍历i的父节点，再遍历i的兄弟节点。随着递归的逐渐出栈，最终完成遍历
 * 先序遍历：即根-左-右遍历
 * 后序遍历：即左-右-根遍历
 *
 * 2.广度优先遍历（BFS），也叫层序遍历
 * 层序遍历需要借助一个队列：要访问的节点全部放到队列里。当访问一个节点时，就让它的子节点入队，依次访问。
 */

public class Erchashubianli {

    /*
                1
              2   3
                 4  5
                  6
     */
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);

        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;
        treeNode4.right = treeNode6;

        Erchashubianli e = new Erchashubianli();
        e.printTreePreOrder(treeNode1);
        System.out.println();
        e.printTreeInOrder(treeNode1);
        System.out.println();
        e.printTreePostOrder(treeNode1);
        System.out.println();
        e.printTreeLevelOrder(treeNode1);
    }

    //先序遍历
    public void printTreePreOrder(TreeNode treeNode){
        if(treeNode == null) return;

        System.out.print(treeNode.val);//先打印本节点
        printTreePreOrder(treeNode.left);//再打印左子树
        printTreePreOrder(treeNode.right);//最后打印右子树
    }

    //中序遍历
    public void printTreeInOrder(TreeNode treeNode){
        if(treeNode == null) return;

        printTreeInOrder(treeNode.left);//先打印左子树
        System.out.print(treeNode.val);//再打印本节点
        printTreeInOrder(treeNode.right);//最后打印右子树
    }

    //后序遍历
    public void printTreePostOrder(TreeNode treeNode){
        if(treeNode == null) return;

        printTreePostOrder(treeNode.left);//先打印左子树
        printTreePostOrder(treeNode.right);//再打印右子树
        System.out.print(treeNode.val);//最后打印本节点
    }

    //层序遍历
    public void printTreeLevelOrder(TreeNode treeNode){
        //创建一个队列
        Deque<TreeNode> queue = new ArrayDeque<>();

        //将根节点入队
        queue.offer(treeNode);

        //循环做出队，打印并入队左子节点，入队右子节点的操作，知道队列为空
        while(!queue.isEmpty()){
            TreeNode curr = queue.poll();
            System.out.print(curr.val);
            if(curr.left != null) queue.offer(curr.left);
            if(curr.right != null) queue.offer(curr.right);
        }
    }
}
